#pragma once
#include<string>
#include"BitSet.h"

//下面三个字符串转换成整形的仿函数

struct HashFuncBKDR
{
	// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》
	// 一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法累乘因子为31。
	size_t operator()(const std::string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash *= 31;
			hash += ch;
		}
		return hash;
	}
};

struct HashFuncAP
{
	// 由Arash Partow发明的一种hash算法。  
	size_t operator()(const std::string& s)
	{
		size_t hash = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0) // 偶数位字符
			{
				hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
			}
			else              // 奇数位字符
			{
				hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
			}
		}

		return hash;
	}
};

struct HashFuncDJB
{
	// 由Daniel J. Bernstein教授发明的一种hash算法。 
	size_t operator()(const std::string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash = hash * 33 ^ ch;
		}

		return hash;
	}
};

 // 布隆过滤器的实现
template<size_t N,  //最多存储的数据个数。
	size_t X = 5, //平均存储一个值，需开辟X个位，该值根据前面公式得来，此时哈希函数是3个，故m=3n/ln2=4.3n，向上取整后X为5，先给个缺省值是5。
	class K = std::string, //布隆过滤器处理的数据类型，默认情况下是string，也可以是其他类型。
	class Hash1 = HashFuncBKDR, //哈希函数：将字符串或者其他类型转换成整形进行映射，给的缺省值是将字符串转换成整形的仿函数。
	class Hash2 = HashFuncAP,
	class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
	//标记一个字符串是否存在
	void Set(const K& key)
	{
		// 将一个字符串转换成三个整型
		size_t hash1 = Hash1()(key) % M;
		size_t hash2 = Hash2()(key) % M;
		size_t hash3 = Hash3()(key) % M;

		//cout << hash1 <<" "<< hash2 <<" "<< hash3 << endl;

		// 进行三次映射
		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

	// 判断每个比特位时，判断它不存在，注：不要判断它存在，因为不存在是准确的，存在是不准确的。
	bool Test(const K& key)
	{
		size_t hash1 = Hash1()(key) % M;
		if (!_bs.test(hash1))
		{
			return false;
		}

		size_t hash2 = Hash2()(key) % M;
		if (!_bs.test(hash2))
		{
			return false;
		}

		size_t hash3 = Hash3()(key) % M;
		if (!_bs.test(hash3))
		{
			return false;
		}

		return true; // 可能存在误判
	}

	// 获取公式计算出的误判率
	double getFalseProbability()
	{
		double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);

		return p;
	}


private:
	static const size_t M = N * X;
	bit::bitset<M> _bs;
};



void TestBloomFilter1()
{
	BloomFilter<10> bf1;
	bf1.Set("island");
	bf1.Set("sun");
	bf1.Set("moon");

	printf("%d\n", bf1.Test("island"));
	printf("%d\n", bf1.Test("sun"));
	printf("%d\n\n", bf1.Test("Sun"));

	BloomFilter<10> bf2;
	bf2.Set("猪八戒");
	bf2.Set("孙悟空");
	bf2.Set("唐僧");

	cout << bf2.Test("猪八戒") << endl;
	cout << bf2.Test("孙悟空") << endl;
	cout << bf2.Test("唐僧") << endl;
	cout << bf2.Test("沙僧") << endl;
	cout << bf2.Test("猪八戒1") << endl;
	cout << bf2.Test("猪戒八") << endl;
}


void TestBloomFilter2()
{
	srand(time(0));
	const size_t N = 10000;
	//BloomFilter<N> bf;
	//BloomFilter<N, 3> bf;
	BloomFilter<N, 10> bf;
    //std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
    //std::string url = "https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=ln2&fenlei=256&rsv_pq=0x8d9962630072789f& rsv_t=ceda1rulSdBxDLjBdX4484KaopD%2BzBFgV1uZn4271RV0PonRFJm0i5xAJ%2FDo&rqlang=en&rsv_enter=1&rsv_dl=ib&rsv_sug3=3&rsv_sug1=2&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&inputT=330&rsv_sug4=2535";
	
    std::vector<std::string> v1;
	std::string url = "猪八戒";

	for (size_t i = 0; i < N; ++i) 
	{
		v1.push_back(url + std::to_string(i));
	}
	for (auto& str : v1)
	{
		bf.Set(str);
	}

	// v2跟v1是相似字符串集（前缀一样），但是后缀不一样
	v1.clear();
	for (size_t i = 0; i < N; ++i)
	{
		std::string urlstr = url;
		urlstr += std::to_string(9999999 + i);
		v1.push_back(urlstr);
	}
	size_t n2 = 0;
	for (auto& str : v1)
	{
		if (bf.Test(str)) // 误判
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
	// 不相似字符串集  前缀后缀都不一样
	v1.clear();
	for (size_t i = 0; i < N; ++i)
	{
		string url = "孙悟空";
		url += std::to_string(i + rand());
		v1.push_back(url);
	}
	size_t n3 = 0;
	for (auto& str : v1)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
	cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}


